package com.liunian.algorithmstudy.str;

public class LongestPalindrome {

    public String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        char[] newChars = preProcess(chars);
        int n = newChars.length;
        int[] results = new int[n];
        int center = 0;
        int right = 0;
        for (int i = 1; i < n - 1; i++) {
            int i_mirror = 2 * center - i;
            if (i < right) {
                results[i] = Math.min(right - i, results[i_mirror]);
            }
            while (newChars[i + 1 + results[i]] == newChars[i - 1 - results[i]]) {
                results[i]++;
            }
            if (i + results[i] > right) {
                center = i;
                right = i + results[i];
            }
        }
        int index = 0;
        int len = 0;
        for (int i = 1; i < n; i++) {
            if (results[i] > len) {
                len = results[i];
                index = i;
            }
        }
        int left = (index - len) / 2;
        return new String(chars, left, len);
    }

    private char[] preProcess(char[] chars) {
        char[] newChars = new char[2 * chars.length + 3];
        newChars[0] = '^';
        newChars[newChars.length - 1] = '$';
        newChars[newChars.length - 2] = '#';
        for (int i = 0; i < chars.length; i++) {
            newChars[2 * i + 1] = '#';
            newChars[2 * (i + 1)] = chars[i];
        }
        return newChars;
    }

    public String longestPalindrome2(String s) {
        char[] chars = s.toCharArray();
        int n = s.length();
        int left = 0;
        int maxLen = 1;
        for (int i = 0; i < n; i++) {
            int len1 = palindromeLen(chars, i, i);
            int len2 = palindromeLen(chars, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > maxLen) {
                maxLen = len;
                left = i - (len - 1) / 2;
            }
        }
        return new String(chars, left, maxLen);
    }


    private int palindromeLen(char[] chars, int left, int right) {
        while (left >= 0 && right < chars.length && chars[left] == chars[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }


    public static void main(String[] args) {
        LongestPalindrome palindrome = new LongestPalindrome();
        System.out.println(palindrome.longestPalindrome2("a"));
    }
}
